package com.tang.algorithm.swordFingerOffer;

import java.util.HashMap;
import java.util.LinkedHashMap;

/**
 * @author tlm
 * @version 1.0
 * @date 2020/5/6 21:14
 * 第一个只出现一次的字符
 * <p>
 * https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/
 */
public class CharactersThatAppearOnlyOnce {
    public static void main(String[] args) {
        System.out.println(firstUniqChar2("aabccddeefgcdddzdc"));
    }

    /**
     * 解法1 使用HashMap 执行时间击败27.8%
     * @param s
     * @return
     */
    public static char firstUniqChar(String s) {
        HashMap<Character, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            Character key = s.charAt(i);
            if (hashMap.containsKey(key)) {
                int times = hashMap.get(key);
                hashMap.put(key, ++times);
            } else {
                hashMap.put(key, 1);
            }
        }
        for (int i = 0; i < s.length(); i++) {
            Character key = s.charAt(i);
            if (hashMap.get(key) == 1) {
                return key;
            }
        }
        return ' ';
    }
    /**
     * 解法2 使用LinkedHashMap 执行时间击败57.46%
     * @param s
     * @return
     */
    public static char firstUniqChar2(String s) {
        LinkedHashMap<Character,Boolean> hashMap = new LinkedHashMap<>();
        char[] chars = s.toCharArray();
        for(char c:chars){
            hashMap.put(c,!hashMap.containsKey(c));
        }
        for(char c:chars){
            if(hashMap.get(c)) return c;
        }
        return ' ';
    }


}
